package com.atues.backtrack.restoreIpAddresses;

import java.util.ArrayList;
import java.util.List;

class Solution {

    List<String> res = new ArrayList<String>();


    public List<String> restoreIpAddresses(String s) {
        backtracking(s,0,0);
        return res;
    }
    public void backtracking(String s,int start,int pointSum){
        if(pointSum == 3){
            if(check(s,start,s.length())){
                res.add(s);
            }
            return;
        }

        for(int i = start ; i < s.length() && i - start <= 3; i++){
            if(check(s,start,i+1)){
               s = s.substring(0,i+1) + "." + s.substring(i+1);
               pointSum ++;
                backtracking(s, i + 2, pointSum);
                pointSum --;
                s = s.substring(0,i+1) + s.substring(i+2);
            }

        }
    }

    public boolean check(String s, int start, int end) {
        if(start >= s.length() || end >= s.length()+1 || end - start > 3)return false;
        if(s.charAt(start) == '0'){
            if(end - start > 1)return false;
            else return true;
        }

        String substring = s.substring(start, end);
        Integer i = new Integer(substring);
        if(i < 0 || i > 255)return false;
        return true;
    }
}